0764. 最大加号标志【中等】

• 1. 📝 题目描述
• 2. 🎯 s.1 - 动态规划

1. 📝 题目描述

• leetcode

在一个 n x n 的矩阵 grid 中，除了在数组 mines 中给出的元素为 0，其他每个元素都为 1。mines[i] = [xi, yi]表示 grid[xi][yi] == 0

返回 grid 中包含 1 的最大的 轴对齐 加号标志的阶数。如果未找到加号标志，则返回 0。

一个 k 阶由 1 组成的 “轴对称”加号标志 具有中心网格 grid[r][c] == 1，以及 4 个从中心向上、向下、向左、向右延伸，长度为 k-1，由 1 组成的臂。注意，只有加号标志的所有网格要求为 1，别的网格可能为 0 也可能为 1。

---

示例 1：

输入: n = 5, mines = [[4, 2]]
输出: 2

解释:
在上面的网格中，最大加号标志的阶只能是2。一个标志已在图中标出。

---

示例 2：

输入: n = 1, mines = [[0, 0]]
输出: 0

解释:
没有加号标志，返回 0。

---

提示：

• 1 <= n <= 500
• 1 <= mines.length <= 5000
• 0 <= xi, yi < n
• 每一对 (xi, yi) 都 不重复 ​​​​​​​

2. 🎯 s.1 - 动态规划

c

int orderOfLargestPlusSign(int n, int** mines, int minesSize, int* minesColSize) {
    int** grid = (int**)malloc(sizeof(int*) * n);
    int** dp = (int**)malloc(sizeof(int*) * n);
    for (int i = 0; i < n; i++) {
        grid[i] = (int*)malloc(sizeof(int) * n);
        dp[i] = (int*)calloc(n, sizeof(int));
        for (int j = 0; j < n; j++) grid[i][j] = 1;
    }
    for (int i = 0; i < minesSize; i++) grid[mines[i][0]][mines[i][1]] = 0;
    int res = 0;
    for (int i = 0; i < n; i++) {
        int cnt = 0;
        for (int j = 0; j < n; j++) { cnt = grid[i][j] ? cnt + 1 : 0; dp[i][j] = cnt; }
        cnt = 0;
        for (int j = n - 1; j >= 0; j--) { cnt = grid[i][j] ? cnt + 1 : 0; if (cnt < dp[i][j]) dp[i][j] = cnt; }
    }
    for (int j = 0; j < n; j++) {
        int cnt = 0;
        for (int i = 0; i < n; i++) { cnt = grid[i][j] ? cnt + 1 : 0; if (cnt < dp[i][j]) dp[i][j] = cnt; }
        cnt = 0;
        for (int i = n - 1; i >= 0; i--) { cnt = grid[i][j] ? cnt + 1 : 0; if (cnt < dp[i][j]) dp[i][j] = cnt; if (dp[i][j] > res) res = dp[i][j]; }
    }
    for (int i = 0; i < n; i++) { free(grid[i]); free(dp[i]); }
    free(grid); free(dp);
    return res;
}

js

/**
 * @param {number} n
 * @param {number[][]} mines
 * @return {number}
 */
var orderOfLargestPlusSign = function (n, mines) {
  const grid = Array.from({ length: n }, () => new Array(n).fill(1))
  for (const [r, c] of mines) grid[r][c] = 0
  const dp = Array.from({ length: n }, () => new Array(n).fill(0))
  let res = 0
  for (let i = 0; i < n; i++) {
    // left
    let cnt = 0
    for (let j = 0; j < n; j++) {
      cnt = grid[i][j] ? cnt + 1 : 0
      dp[i][j] = cnt
    }
    // right
    cnt = 0
    for (let j = n - 1; j >= 0; j--) {
      cnt = grid[i][j] ? cnt + 1 : 0
      dp[i][j] = Math.min(dp[i][j], cnt)
    }
  }
  for (let j = 0; j < n; j++) {
    // up
    let cnt = 0
    for (let i = 0; i < n; i++) {
      cnt = grid[i][j] ? cnt + 1 : 0
      dp[i][j] = Math.min(dp[i][j], cnt)
    }
    // down
    cnt = 0
    for (let i = n - 1; i >= 0; i--) {
      cnt = grid[i][j] ? cnt + 1 : 0
      dp[i][j] = Math.min(dp[i][j], cnt)
      res = Math.max(res, dp[i][j])
    }
  }
  return res
}

py

class Solution:
    def orderOfLargestPlusSign(self, n: int, mines: List[List[int]]) -> int:
        grid = [[1] * n for _ in range(n)]
        for r, c in mines:
            grid[r][c] = 0
        dp = [[0] * n for _ in range(n)]
        for i in range(n):
            cnt = 0
            for j in range(n):
                cnt = cnt + 1 if grid[i][j] else 0
                dp[i][j] = cnt
            cnt = 0
            for j in range(n - 1, -1, -1):
                cnt = cnt + 1 if grid[i][j] else 0
                dp[i][j] = min(dp[i][j], cnt)
        res = 0
        for j in range(n):
            cnt = 0
            for i in range(n):
                cnt = cnt + 1 if grid[i][j] else 0
                dp[i][j] = min(dp[i][j], cnt)
            cnt = 0
            for i in range(n - 1, -1, -1):
                cnt = cnt + 1 if grid[i][j] else 0
                dp[i][j] = min(dp[i][j], cnt)
                res = max(res, dp[i][j])
        return res

• 时间复杂度：$O(n^2)$
• 空间复杂度：$O(n^2)$

算法思路：

• 对每个位置分别计算上、下、左、右四个方向的连续 1 的最大长度
• 取四个方向的最小值作为该位置的加号阶数
• 所有位置中的最大值即为答案